1. Field of the Invention
This invention relates to cryptographic systems for electronic transfer of information, and more specifically to methods for improving the practicality and the security of such systems.
2. Description of the Prior Art
In a public-key cryptographic system for electronic transfer of information, a user party performs a cryptographic action (meaning a cryptographic task that can only be performed knowing a secret key) with respect to a public key that has been issued or validated by an issuing party. The cryptographic action can be verified off-line by a receiver party if the public key is accompanied by a digital certificate of the issuing party on the public key. When the verification is performed on-line by the issuing party, and the issuing party can recognize the public keys it issued, no digital certificate is needed.
In order to perform public-key cryptographic computations each party must have at least one computing device at its disposal. Any one of the following three configurations may be used by a user party: a tamper-resistant computing device; a computing device that the user party, at least in principle, can fully control, henceforth referred to as a user-controlled computing device; or, both a tamper-resistant computing device and a user-controlled computing device. A tamper-resistant computing device offers security for the party in whose interest it acts, typically the issuing party, when the decision of whether to perform the cryptographic action may not be made by the user party itself. An access control mechanism for the tamper-resistant computing device offers protection to the user party against loss or theft. The use of a user-controlled computing device is appropriate when communication between the computing device of the user party and the outside world can only be handled satisfactorily by a desktop computer or the like, or when the secret key of the computing device may be known to the user without loss of security. The use of a tamper-resistant computing device together with a user-controlled computing device offers the advantage of both; the tamper-resistant device offers security and, when it is small, convenient portability between application platforms, and the user-controlled device offers ease of communication and secure data entry and display means for the user party.
An important example of a public-key cryptographic system for electronic transfer of certified information is an electronic payment system. In a first type of electronic payment system, a digital signature provided by a computing device of a user party serves as a promise-to-pay, validating for example a debit or credit card payment. Because no value is stored by the computing device, the user party can be allowed to know the secret key of its computing device, and any one of the three abovementioned configurations can be used.
A second type of electronic payment system is a pre-paid, electronic purse system. Here, a computing device of a user party maintains a counter, representing the amount of electronic cash held by the user party. To transfer an amount, the computing device digitally signs with respect to its public key a message specifying at least the amount, and correspondingly decreases its counter. To prevent the user party from making payments without involvement of the counter, the computing device must be tamper-resistant.
A third type of electronic payment system is one in which payments of a user party are untraceable and, at least to some degree, unlinkable. Value is represented either by a counter in a tamper-resistant device, or in the form of digital coins. Privacy of electronic payments can be attained in either one of two different ways: stored-value tamper-resistant computing devices are issued anonymously (for untraceability), and may be freely exchanged amongst user parties (for unlinkability); or suitable cryptographic techniques are used for blinding digital coins when issued.
While much research has been done to improve the security and practicality of public-key cryptographic systems for electronic transfer of information, several shortcomings have not yet been addressed or overcome.
A first problem relates to the fact that a smart card or a PCMCIA card, which are typical embodiments for a tamper-resistant computing device, can rapidly perform a cryptographic action such as digital signing only by using a special-purpose cryptoprocessor; ordinary 4 or 8-bit micro-processors typically take many minutes. To improve efficiency somewhat, a digital signature scheme can be used for which the bulk of the required computations can be pre-processed, and the remaining task can be performed efficiently by a simple processor. This improvement is not satisfactory for applications where signatures frequently need to be produced at substantially unpredictable moments. Server-aided computation does not allow delegation of the pre-processing phase to an untrusted powerful processor to such an extent that a non-sophisticated processor can rapidly perform the remaining computational task. Delegation of the pre-processing phase to a powerful processor of a trusted party that knows the secret key of the tamper-resistant device (See, Naccache, D., M'Raihi, D., Raphaeli, D., and Vaudenay, S., "Can D.S.A. be Improved? -Complexity Trade-Offs with the Digital Signature Standard-," Pre-proceedings of Eurocrypt '94, pp. 85-94) suffers from the following problems: the tamper-resistant device needs to store all pre-computed values in EEPROM, which is fairly limited for ordinary smart card processors; (re-)loading the card with pre-computed values requires bringing it into direct contact with a terminal of the issuing party, which is often inconvenient, and enables the smart card to send privacy-related information to the trusted party and vice versa; and, the trusted party has the ability to forge signatures with respect to the public key of the tamper-resistant computing device, since it knows the secret key used by the tamper-resistant computing device to perform its cryptographic action.
Another problem is the potential damage due to loss or theft of computing devices. While password or biometric verification may prevent opportune criminals from operating computing devices of other parties, it certainly does not protect against determined criminals who can by-pass password or biometric verification mechanisms. The expected damage caused by such criminals can be limited somewhat by requiring user parties to report stolen or lost computing devices, and correspondingly distribute blacklists, but this measure is not entirely satisfactory for large-scale applications.
A third problem relates to the setting in which a user party holds both a user-controlled computing device and a tamper-resistant computing device. In this setting the tamper-resistant computing device typically holds a secret key needed to perform the cryptographic action, and the user-controlled computing device serves mainly as a convenient interface to the outside world and to offer secure data entry and display means to the user party. An access control mechanism does not protect sufficiently against loss or theft of the tamper-resistant device, since determined criminals can be expected to be able to by-pass that. Storing the public key of the tamper-resistant computing device and, if present, an issued digital certificate thereon, only in the user-controlled computing device hardly improves security, because they can be learned by wire-tapping, or participating in, an execution of the cryptographic action performed by the tamper-resistant device.
Other problems relate specifically to privacy-protected off-line electronic payment systems. When value is represented by counters in tamper-resistant computing devices, which can be obtained anonymously and may be exchanged freely amongst user parties, it is awkward to trace fraudulent parties that have managed to by-pass counters, inconvenient to reload devices anonymously (other anonymously obtained tokens must be given in exchange), and devices cannot be protected with an access control mechanism. When privacy is obtained by applying cryptographic techniques for blinding issued digital coins, such as described and claimed for example in patent application Ser. No. 08/203,231, filed Feb. 28, 1994, amounts frequently can be paid only by using many digital coins, and it is possible to have digital coins at ones disposal without being able to pay a specified amount. To overcome the problems of counter-based systems on the one hand, and of digital coins on the other hand, a privacy-protected off-line payment system has been proposed in the prior art in which value is represented by counters, while payments are made using blindly issued digital cheques (See, Bos, J., and Chaum, D., "SmartCash: A Practical Electronic Payment System," Centrum voor Wiskunde en Informatica, Report CS-R9035, August 1990. See also, Chaum, D., "Optionally moderated transaction systems," patent Ser. No. 5276736). A serious problem of this system is that a determined criminal, who manages to extract the contents of his tamper-resistant computing device, can spend withdrawn cheques over and over again, without being traceable; anonymous publication of the contents of a compromised tamper-resistant device can seriously cripple the system. No privacy-protected off-line electronic payment system is known that overcomes the practical problems associated with digital coins without significantly degrading security.
Another problem with the known privacy-protected off-line payment systems based on the blinding concept is that they do not offer the possibility of currency conversion. In cross-boundary payment applications this may pose a serious problem to the acceptability of these systems.